package pri.zjy.tree;

import pri.zjy.tree.model.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zhangjy
 * @description 二叉搜索树中第 K 小的元素
 * <p>
 * 给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（从 1 开始计数）。
 * <p>
 * 提示：
 * <p>
 * 树中的节点数为 n 。
 * 1 <= k <= n <= 104
 * 0 <= Node.val <= 104
 * <p>
 * <p>
 * 进阶：如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化算法？
 * @date 2025/3/7 10:02
 */
public class KthSmallest_230 {

    public static void main(String[] args) {

        // TODO 栈（参考官解）

        KthSmallest_230 kthSmallest230 = new KthSmallest_230();

        TreeNode two = new TreeNode(2);
        TreeNode one = new TreeNode(1, null, two);
        TreeNode four = new TreeNode(4);
        TreeNode three = new TreeNode(3, one, four);

        System.out.println(kthSmallest230.kthSmallest3(three, 1));
    }

    Integer res;

    Integer globalK;

    /**
     * 法三：力扣题解-递归（正确，通过全局变量控制）
     * <p>
     * 题解：https://leetcode.cn/problems/kth-smallest-element-in-a-bst/solutions/2361685/230-er-cha-sou-suo-shu-zhong-di-k-xiao-d-n3he
     */
    public int kthSmallest3(TreeNode root, int k) {
        // 个人解法：参考题解
        globalK = k;
        return recurse3(root);

        // 题解：
//        globalK = k;
//        recurse4(root);
//        return res;
    }

    public Integer recurse3(TreeNode root) {
        if (root == null) return null;

        recurse3(root.left);
        if (globalK == 0) return res;
        // 全局变量记录k值，以及找到的第k小的元素。
        if (--globalK == 0) {
            res = root.val;
            return res;
        }
        recurse3(root.right);
        return res;
    }

    public void recurse4(TreeNode root) {
        if (root == null) return;

        recurse4(root.left);
        if (globalK == 0) return;
        if (--globalK == 0) {
            res = root.val;
            return;
        }
        recurse4(root.right);
    }


    /**
     * 法二：官解-递归（错误，局部变量一直在变化）
     * <p>
     * 分析：法一先中序遍历，再获取目标元素，其实是你要找第k小的元素，那我就先知道所有元素排序，这样就能直接找到；
     * 但是这样每次查找都会遍历整棵树，对于一颗经常被修改的BST，时间花费也较多。
     * <p>
     * 考虑能否在递归的过程中，就可以知道当前元素是第 k 小。
     * <p>
     * 根据BST中序遍历递归的思想，取节点值val的顺序，就是最后严格递增vals的顺序；所以，在取val时就可以记录个数，当取到第 k 个元素时，该元素就是第 k 小。
     * <p>
     */
    public int kthSmallest2(TreeNode root, int k) {
        // 该解法错误！！！
        // 因为，k作为局部变量，本层--k后回到上层，上层仍是初始值；
        // 如k=1，第2层--k后，k=0，但是回到第一层时k仍然为1，这里就有问题

        return recurse2(root, k, root.val);
    }

    public Integer recurse2(TreeNode root, int k, Integer res) {
        // 1.返回值、入参
        // 返回值：第k小的元素；入参：节点，k

        // 2.终止条件
        // 当前节点为null，终止本层递归；
        // 记录到第k个，就终止本层递归
        if (root == null) return null;
        // 这个终止条件移到下面去，为什么？
//        if (k == 0) return res;


        // 3.单层逻辑
        // 左—>根—>右；左、右递归到下层，每次根时，中序遍历就代表会记录一次节点值val，就会执行k--，且这里不用记录节点值到list
        recurse2(root.left, k, res);
        // 直接结束本层循环，退到上一层
        if (k == 0) return res;
        if (--k == 0) {
            res = root.val;
            return res;
        }
        recurse2(root.right, k, res);
        return res;
    }

    /**
     * 法一：根据BST及中序遍历特点，先中序得到所有节点值，再取对应下标val；
     * <p>
     * 分析：BST中序遍历得到的节点值vals是严格递增，那么求第k小的值，也就转化为获取vals下标k-1的元素。
     * <p>
     * <p>
     * 时间复杂度：T(n) = O(n)；
     * <p>
     * 递归遍历耗时O(n)，其中 n 为二叉树节点的个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次；list获取指定下标元素耗时O(1)。
     * <p>
     * 空间复杂度：S(n) = O(n);
     * <p>
     * 空间复杂度取决于递归的栈深度，而栈深度在二叉树为一条链的情况下会达到 O(n) 的级别。
     */

    public int kthSmallest(TreeNode root, int k) {
        if (k < 0) return -1;

        // 1.中序遍历得到节点值集合（严格递增）
        List<Integer> vals = inorder(root, new ArrayList<>());

        if (k > vals.size()) return -1;
        // 2.获取下标k-1的元素
        return vals.get(k - 1);
    }

    public List<Integer> inorder(TreeNode root, List<Integer> vals) {
        // 返回值、入参

        // 终止条件：当前节点为null
        if (root == null) return vals;

        // 单层逻辑：左—>根—>右，左、右继续向下递归，根则记录根节点val
        inorder(root.left, vals);
        vals.add(root.val);
        inorder(root.right, vals);

        return vals;
    }

}
